/**
 * 给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏。
 *
 * 玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。每一回合，玩家从数组的任意一端取一个数字（即，nums[0] 或 nums[nums.length - 1]），取到的数字将会从数组中移除（数组长度减 1 ）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。
 *
 * 如果玩家 1 能成为赢家，返回 true 。如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true 。你可以假设每个玩家的玩法都会使他的分数最大化。
 * 链接：https://leetcode.cn/problems/predict-the-winner/description/
 * 题解：https://labuladong.gitee.io/algo/3/28/93/
 */
class PredictTheWinner {
    /**
     * 法一：递归搜索，dfs(i,n-1)表示，在i,n-1中先手减去后手的分数
     */
    int[][] memo;
    public boolean PredictTheWinnerDp(int[] nums) {
        int n=nums.length;
        memo=new int[n][n];
        for(int[] row:memo) {
            Arrays.fill(row,-1);
        }
        return dfs(nums,0,n-1)>=0;
    }
    public int dfs(int[] nums,int i,int j) {
        if(i>j) {
            return 0;
        }
        if(memo[i][j]!=-1) {
            return memo[i][j];
        }
        int left=nums[i]-dfs(nums,i+1,j);
        int right=nums[j]-dfs(nums,i,j-1);
        memo[i][j]=Math.max(left,right);
        return memo[i][j];
    }

    /**
     * 法二：动态规划
     * dp[i][j].fir = x 表示，对于 piles[i...j] 这部分石头堆，先手能获得的最高分数为 x。
     *
     * dp[i][j].sec = y 表示，对于 piles[i...j] 这部分石头堆，后手能获得的最高分数为 y。
     *
     * 举例理解一下，假设 piles = [2, 8, 3, 5]，索引从 0 开始，那么：
     *
     * dp[0][1].fir = 8 意味着：面对石头堆 [2, 8]，先手最多能够获得 8 分；dp[1][3].sec = 5 意味着：面对石头堆 [8, 3, 5]，后手最多能够获得 5 分。
     *
     * 我们想求的答案是先手和后手最终分数之差，按照这个定义也就是 dp[0][n-1].fir - dp[0][n-1].sec，即面对整个 piles，先手的最优得分和后手的最优得分之差。
     * dp[i][j].fir = max(piles[i] + dp[i+1][j].sec, piles[j] + dp[i][j-1].sec)
     * dp[i][j].fir = max(     选择最左边的石头堆     ,     选择最右边的石头堆      )
     * # 解释：我作为先手，面对 piles[i...j] 时，有两种选择：
     * # 要么我选择最左边的那一堆石头，然后面对 piles[i+1...j]
     * # 但是此时轮到对方，相当于我变成了后手；
     * # 要么我选择最右边的那一堆石头，然后面对 piles[i...j-1]
     * # 但是此时轮到对方，相当于我变成了后手。
     *
     * if 先手选择左边:
     *     dp[i][j].sec = dp[i+1][j].fir
     * if 先手选择右边:
     *     dp[i][j].sec = dp[i][j-1].fir
     * # 解释：我作为后手，要等先手先选择，有两种情况：
     * # 如果先手选择了最左边那堆，给我剩下了 piles[i+1...j]
     * # 此时轮到我，我变成了先手；
     * # 如果先手选择了最右边那堆，给我剩下了 piles[i...j-1]
     * # 此时轮到我，我变成了先手。
     * 根据 dp 数组的定义，我们也可以找出 base case，也就是最简单的情况：
     * dp[i][j].fir = piles[i]
     * dp[i][j].sec = 0
     * 其中 0 <= i == j < n
     * # 解释：i 和 j 相等就是说面前只有一堆石头 piles[i]
     * # 那么显然先手的得分为 piles[i]
     * # 后手没有石头拿了，得分为 0
     * 这里需要注意一点，我们发现 base case 是斜着的，而且我们推算 dp[i][j] 时需要用到 dp[i+1][j] 和 dp[i][j-1]
     *  判断 dp 数组遍历方向的原则，算法应该倒着遍历 dp 数组
     * @param nums
     * @return
     */
     public boolean PredictTheWinner(int[] nums) {
         return stoneGame(nums)>=0;
     }
     public int stoneGame(int[] piles) {
         int n=piles.length;
         Pair[][] dp=new Pair[n][n];
         for(int i=0;i<n;i++) {
             for(int j=i;j<n;j++) {
                 dp[i][j]=new Pair(0,0);
             }
         }
         for(int i=0;i<n;i++) {
             dp[i][i].fir=piles[i];
             dp[i][i].sec=0;
         }
         for(int i=n-2;i>=0;i--) {
             for(int j=i+1;j<n;j++) {
                 //先手选择最左边或最右边的分数
                 int left=piles[i]+dp[i+1][j].sec;
                 int right=piles[j]+dp[i][j-1].sec;
                 //套用转移方程，先手肯定选择更大的结果，后手的选择随之改变
                 if(left>right) {
                     dp[i][j].fir=left;
                     dp[i][j].sec=dp[i+1][j].fir;
                 } else {
                     dp[i][j].fir=right;
                     dp[i][j].sec=dp[i][j-1].fir;
                 }
             }
         }
         Pair res=dp[0][n-1];
         return res.fir-res.sec;
     }
}
class Pair{
    int fir,sec;
    Pair(int fir,int sec) {
        this.fir=fir;
        this.sec=sec;
    }
}